class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] preSums = new long[nums.length + 1];
        preSums[0] = 0; // preSums[0] is 0 by definition
        // preSums array initialization
        for (int i = 0; i < nums.length; i ++) {
            preSums[i+1] = preSums[i] + nums[i];

        }
        // call count the number of RangeSum by recurrsive function
        return countRecur(preSums, 0, preSums.length-1, lower , upper);
    }
    private int countRecur(long[] sums, int left, int right, int lower, int upper) {
        if (left == right) return 0; // end of recurrsive
        else {
            int mid = (left + right) /2;
            int ans; // number of Range Sum by left part and right part of the array
            int n1 = countRecur(sums, left, mid, lower, upper);
            int n2 = countRecur(sums, mid+1, right, lower, upper);
            ans = n1 + n2;
            // count the number of Range sum by index of sums
            // which between the lower and upper bounds
            int l = mid + 1;
            int r = mid + 1;
            int i = left;
            while (i <= mid) {
                while (l<=right && sums[l] - sums[i] < lower) {
                    l++;
                }
                while (r<=right && sums[r] - sums[i] <= upper) {
                    r++;
                }
                i++;
                ans += r - l;
            }
            

            //merge and sort the arrsys
            long merged[] = new long[right - left + 1];
            int p1 = left;
            int p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {  // end of left part
                    merged[p++] = sums[p2++];
                } else if (p2 > right) { // end of the right part
                    merged[p++] = sums[p1++];
                } else { // normal case
                    if (sums[p1] > sums[p2]) { // pick up the smaller into the merged array
                        merged[p++] = sums[p2++];

                    }   else {

                         merged[p++] = sums[p1++];

                    } 

                }


            }
            // put the merged and sorted array to sums array
            for (int j = 0; j < merged.length; j++) {
                sums[left+j] = merged[j];
            }


            return ans;
        }




    }
}